1. Field of the Invention
The present invention relates generally to digital image processing and, more particularly, to improved techniques for compression of digital images.
2. Description of the Background Art
Today, digital imaging, particularly in the form of digital cameras, is a prevalent reality that affords a new way to capture photos using a solid-state image sensor instead of traditional film. A digital camera functions by recording incoming light on some sort of sensing mechanism and then processes that information (basically, through analog-to-digital conversion) to create a memory image of the target picture. A digital camera's biggest advantage is that it creates images digitally thus making it easy to transfer images between all kinds of devices and applications. For instance, one can easily insert digital images into word processing documents, send them by e-mail to friends, or post them on a Web site where anyone in the world can see them. Additionally, one can use photo-editing software to manipulate digital images to improve or alter them. For example, one can crop them, remove red-eye, change colors or contrast, and even add and delete elements. Digital cameras also provide immediate access to one's images, thus avoiding the hassle and delay of film processing. All told, digital photography is becoming increasingly popular because of the flexibility it gives the user when he or she wants to use or distribute an image.
The defining difference between digital cameras and those of the film variety is the medium used to record the image. While a conventional camera uses film, digital cameras use an array of digital image sensors. When the shutter opens, rather than exposing film, the digital camera collects light on an image sensor, a solid-state electronic device. The image sensor contains a grid of tiny photosites that convert light shining on them to electrical charges. The image sensor may be of the charged-coupled device (CCD) or complementary metal-oxide semiconductor (CMOS) variety. During camera operation, an image is focused through the camera lens so that it will fall on the image sensor. Depending on a given image, varying amounts of light hit each photosite, resulting in varying amounts of electrical charge at the photosites. These charges can then be measured and converted into digital information that indicates how much light hit each site which, in turn, can be used to recreate the image. When the exposure is completed, the sensor is much like a checkerboard, with different numbers of checkers (electrons) piled on each square (photosite). When the image is read off of the sensor, the stored electrons are converted to a series of analog charges which are then converted to digital values by an Analog-to-Digital (A-to-D) converter, which indicates how much light hit each site which, in turn, can be used to recreate the image.
In order to generate an image of quality that is roughly comparable to a conventional photograph, a substantial amount of information must be captured and processed. For example, a low-resolution 640×480 image has 307,200 pixels. If each pixel uses 24 bits (3 bytes) for true color, a single image takes up about a megabyte of storage space. As the resolution increases, so does the image's file size. At a resolution of 1024×768, each 24-bit picture takes up 2.5 megabytes of storage space. Because of the large size of this information, digital cameras usually do not store a picture in its raw digital format but, instead, apply compression techniques, such as JPEG (Joint Photographic Experts Group) compression, to the image so that it can be stored in a standard-compressed image format (e.g., JPEG File Interchange Format). Compressing images allows the user to save more images on the camera's “digital film,” such as flash memory (available in a variety of specific formats) or other facsimile of film. It also allows the user to download and display those images more quickly.
During compression, data that is duplicated or which has little value is eliminated or saved in a shorter form, greatly reducing a file's size. When the image is then edited or displayed, the compression process is reversed. In digital photography, two forms of compression are used: lossless and lossy. In lossless compression (also called reversible compression), reversing the compression process produces an image having a quality that matches the original source. Although lossless compression sounds ideal, it does not provide much compression. Generally, compressed files are still a third the size of the original file, not small enough to make much difference in most situations. For this reason, lossless compression is used mainly where detail is extremely important as in x-rays and satellite imagery. A leading lossless compression scheme is LZW (Lempel-Ziv-Welch). This is used in GIF and TIFF files and achieves compression ratios of 50 to 90%.
Although it is possible to compress images without losing some quality, it is not practical in many cases. Therefore, all popular digital cameras use a lossy compression scheme. Although lossy compression does not uncompress images to the same quality as the original source, the image remains visually lossless and appears normal. In many situations, such as posting images on the Web, the image degradation is not obvious. The trick is to remove data that is not obvious to the viewer. For example, if large areas of the sky are the same shade of blue, only the value for one pixel needs to be saved along with the locations of where the other identical pixels appear in the image.
Currently, the leading lossy compression scheme is JPEG (Joint Photographic Experts Group) used in JFIF files (JPEG File Interchange Format). For purposes of this document, JPEG compression is used as an example of a DCT based compression scheme. Today, JPEG is the most widely used scheme for compression of digital images in digital cameras. JPEG is a lossy compression algorithm that works by converting the spatial image representation into a frequency map. The scheme typically allows the user to select the degree of compression, with compression ratios between 10:1 and 40:1 being common. Because lossy compression affects the image, most cameras allow the user to choose between different levels of compression. This allows the user to choose between lower compression and higher image quality or greater compression and poorer image quality.
Although the JPEG scheme is widely used and does enable considerable reduction of the size of an image file, it has some drawbacks. One problem with JPEG is that it operates on 8×8 pixel blocks rather than the entire image. This may result in visible “block” artifacts (wherein the boundaries of the 8×8 pixel blocks become visible when the image is decompressed), especially at high compression ratios. To avoid block artifacts, JPEG is typically used at lower compression ratios, which results in larger image files. This means that fewer images may be stored on a digital camera and/or that greater memory resources must be available on the camera.
Relatively large files may also present problems in other applications. For example, large files may be problematic when image information is being transferred wirelessly from a digital camera to another device. In fact, wireless transfer of a digital image may be effectively precluded if the image file is too large because of current bandwidth constraints of most wireless networks. In the emerging market of “wireless imaging,” small file sizes are important to transmit pictures over limited bandwidth public cellular networks (e.g., for storing to a repository or for peer-to-peer sharing). Another example of a need for smaller image file sizes is the print graphics industry. In this industry there is a need for smaller file sizes to enable high-resolution pictures to be shared using modems over ordinary phone lines.
Recently it has been discovered that other compression methods (e.g., wavelet-based compression methods) have been found to offer compression performance that is superior to JPEG. Wavelet-based compression operates on the entire image while JPEG operates on 8×8 pixel blocks. The use of “global” information about an image allows wavelet-based compression to avoid the block artifact problems of JPEG, especially at high compression ratios. For example, the new JPEG2000 standard utilizes a wavelet-based compression method. See e.g., “JPEG 2000 image coding system—Part 1: Core coding system,” recently approved by the International Organization for Standardization as ISO/IEC 15444-1:2000. For purposes of this document, “JPEG2000” refers to this recently approved image coding system utilizing wavelet-based compression and not the prior JPEG standard.
Despite the above limitations of JPEG and the advances offered by wavelet-based compression methods, JPEG continues to be used in digital cameras as the hardware and software systems for JPEG based compression are readily available from a number of vendors. Given that many digital camera manufacturers have already made considerable investments in developing camera components to support JPEG compression, they are reluctant to abandon this investment in order to implement wavelet-based compression. For example, a number of manufacturers have developed custom hardware modules (e.g., Application Specific Integrated Circuits or ASICs) including functionality for JPEG compression. Another reason for continuing use of JPEG by camera manufacturers is the fact that JPEG is supported in almost all applications for image editing, enhancement, and display.
Given the widespread use of JPEG and other DCT based compression schemes, there is considerable interest in a method that will enable improved compression of DCT compressed images (e.g., JPEG images) thereby enabling such images to be more efficiently stored or transmitted. In particular, a method enabling more efficient compression of digital images would be particularly useful for transmission of digital images over limited bandwidth channels, such as wireless channels. Ideally, this improved compression method will also maintain or even improve upon image quality by reducing the impact of block artifacts inherent with the use of JPEG. The present invention fulfills these and other needs.